package com.leecode;

/**
 * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
 * <p>
 * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
 * <p>
 * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出：7 -> 0 -> 8
 * 原因：342 + 465 = 807
 * <p>
 * 和另一题类似,先加,最后进位
 */
public class Leet2 {
	public static void main(String[] args) {
//		System.out.println(new Leetcode2().addTwoNumbers(new ListNode(1), new ListNode(2)).val);

		ListNode listNode = new ListNode(2);
		listNode.next = new ListNode(4);
		listNode.next.next = new ListNode(3);
		ListNode listNode2 = new ListNode(3);
		listNode2.next = new ListNode(6);
		listNode2.next.next = new ListNode(4);
		System.out.println(new Leet2().addTwoNumbers(listNode, listNode2).val);

	}

	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		return recur(l1,l2);
	}
	public ListNode recur(ListNode l1,ListNode l2){
		if(l1==null){
			if(l2==null){
				return null;
			}else{
				return l2;
			}
		}else{
			if(l2==null){
				return l1;
			}else{
				l1.val+=l2.val;
				if(l1.val>=10){
					l1.val%=10;
					if(l1.next==null){
						l1.next=new ListNode(1);
					}else{
						l1.next.val++;
					}
				}
				l1.next=recur(l1.next,l2.next);
				ListNode checkTail=l1.next;
				//优化,只进位>=10的
				while(checkTail!=null && checkTail.val>=10){
					checkTail.val%=10;
					if(checkTail.next==null){
						checkTail.next=new ListNode(1);
					}else{
						checkTail.next.val++;
						checkTail=checkTail.next;
					}
				}
				//这是没有优化的,从头进位到尾
				// ListNode b=l1;
				// while(b!=null){
				//     if(b.val<10){
				//         b=b.next;
				//         continue;
				//     }else{
				//         b.val=b.val%10;
				//         if(b.next!=null){
				//             b.next.val++;
				//         }else{
				//             b.next=new ListNode(1);
				//         }
				//     }
				// }
				return l1;
			}
		}
	}
}


